package com.lw.leetcode.back.c;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * c
 * back
 * 301. 删除无效的括号
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/24 9:35
 */
public class RemoveInvalidParentheses {


    public static void main(String[] args) {
        RemoveInvalidParentheses test = new RemoveInvalidParentheses();

        // ["(())()","()()()"]
//        String str = "()())()";

        // ["(a())()","(a)()()"]
//        String str = "(a)())()";

        String str = "(a)())()((d()(()())b)c()";
//        String str = "x(";

        // [""]
//        String str = ")(";

        List<String> list = test.removeInvalidParentheses(str);
        System.out.println(list);
    }

    private Set<String> set = new HashSet<>();
    private char[] chars;
    private int length;
    private StringBuilder sb;

    public List<String> removeInvalidParentheses(String s) {
        chars = s.toCharArray();
        length = s.length();
        int a = 0;
        int b = 0;
        int item = 0;
        for (char c : chars) {
            if (c == '(') {
                item++;
            } else if (c == ')') {
                item--;
            }
            if (item < 0) {
                b -= item;
                item = 0;
            }
        }
        a += item;
        sb = new StringBuilder(length - a - b);
        find(a, b, 0, 0);
        if (set.isEmpty()) {
            set.add("");
        }
        return new ArrayList<>(set);

    }

    private void find(int a, int b, int item, int index) {
        if (item < 0) {
            return;
        }
        if (index == length) {
            if (a == 0 && b == 0 && item == 0) {
                sb.setLength(0);
                for (char c : chars) {
                    if (c != ' ') {
                        sb.append(c);
                    }
                }
                set.add(sb.toString());
            }
            return;
        }
        char c = chars[index];
        if (c == '(') {
            if (a > 0) {
                char aChar = chars[index];
                chars[index] = ' ';
                find(a - 1, b, item, index + 1);
                chars[index] = aChar;
            }
            find(a, b, item + 1, index + 1);
        } else if (c == ')') {
            if (b > 0) {
                char aChar = chars[index];
                chars[index] = ' ';
                find(a, b - 1, item, index + 1);
                chars[index] = aChar;
            }
            find(a, b, item - 1, index + 1);
        } else {
            find(a, b, item, index + 1);
        }
    }

}
